import java.util.*;

public class BinaryTree {
	static class TreeNode {
		public char  val;
		public int val1;
		public TreeNode left;
		public TreeNode right;

		public TreeNode(char  val) {

			this.val = val;
		}
		public TreeNode (int val) {
			this.val1=val;
		}
	}

	@Override
	public String toString() {
		return "BinaryTree{" +
				"ret=" + ret +
				'}';
	}
	//测试二叉树的最大宽度
	public TreeNode createTree1() {
		TreeNode A=new TreeNode('A');
		TreeNode B=new TreeNode('B');
		TreeNode C=new TreeNode('C');
		TreeNode D=new TreeNode('D');
		TreeNode E=new TreeNode('E');
		TreeNode F=new TreeNode('F');
		TreeNode G=new TreeNode('G');
		TreeNode H=new TreeNode('H');
		TreeNode I=new TreeNode('I');
		TreeNode J=new TreeNode('J');
		TreeNode K=new TreeNode('K');
		TreeNode L=new TreeNode('L');
		TreeNode M=new TreeNode('M');
		TreeNode N=new TreeNode('N');
		TreeNode O=new TreeNode('O');
		A.left=B;
		A.right=C;
		B.left=D;
		B.right=E;
		C.left=F;
		C.right=G;
		D.left=H;
		D.right=I;
		E.left=J;
		E.right=K;
		F.left=L;
		F.right=M;
		G.left=N;
		G.right=O;
		return A;
	}

	public TreeNode createTree() {
		TreeNode A=new TreeNode('A');
		TreeNode B=new TreeNode('B');
		TreeNode C=new TreeNode('C');
		TreeNode D=new TreeNode('D');
		TreeNode E=new TreeNode('E');
		TreeNode F=new TreeNode('F');
		TreeNode G=new TreeNode('G');
		TreeNode H=new TreeNode('H');
		TreeNode P=new TreeNode('P');
		A.left=B;
		A.right=C;
		B.left=D;
		B.right=E;
		C.left=F;
		C.right=G;
		E.right=H;
		D.right=P;
		return A;
	}
	public void preOrder(TreeNode root) {
		if(root==null) return ;
		System.out.print(root.val+" ");
		preOrder(root.left);
		preOrder(root.right);
	}
	//将前序遍历的结果存储在一个列表当中
	List<TreeNode> ret=new ArrayList<>();
	//这个ret就一个如果遇到空的话，就直接返回ret
	//这样没有好好利用这个方法的返回值
	public List<TreeNode> preOrder1(TreeNode root) {
		if(root==null) return ret;
		ret.add(root);
		preOrder1(root.left);
		preOrder1(root.right);
		return ret;
	}
	//每递归一次的时候都会进行new一个ret，为空的话就返回一个空值。
	//每个节点的左子树遍历完成的时候，都会返回给父节点，进行拼接
	public  List<TreeNode> preOrder2(TreeNode root) {
		List<TreeNode> ret=new ArrayList<>();
		if (root==null) return ret;
		ret.add(root);
		List<TreeNode> leftTree=preOrder2(root.left);
		ret.addAll(leftTree);
		List<TreeNode> rightTree=preOrder2(root.right);
		ret.addAll(rightTree);
		return ret;
	}

	public void inOrder(TreeNode root) {
		if(root==null) return ;
		inOrder(root.left);
		System.out.print(root.val+" ");
		inOrder((root.right));
	}
	public  List<TreeNode> inOrder1(TreeNode root) {
		List<TreeNode> ret=new ArrayList<>();
		if (root==null) return ret;
		ret.add(root);
		List<TreeNode> leftTree=preOrder2(root.left);
		ret.addAll(leftTree);
		List<TreeNode> rightTree=preOrder2(root.right);
		ret.addAll(rightTree);
		return ret;
	}


	public void postOrder(TreeNode root) {
		if(root==null) return ;
		postOrder(root.left);
		postOrder(root.right);
		System.out.print(root.val+" ");
	}
	public  List<TreeNode> postOrder1(TreeNode root) {
		List<TreeNode> ret=new ArrayList<>();
		if (root==null) return ret;
		ret.add(root);
		List<TreeNode> leftTree=preOrder2(root.left);
		ret.addAll(leftTree);
		List<TreeNode> rightTree=preOrder2(root.right);
		ret.addAll(rightTree);
		return ret;
	}

	//获取书中节点的个数
	int size(TreeNode root) {
		//遍历节点进行计数也可以
		if(root==null) return 0;
		return size(root.left)+size(root.right)+1;
	}
	int getLeafNodeCount(TreeNode root) {
		//还是老办法，划分为子问题进行求解
		//只要判断好结束的条件以及返回值就行了
		if(root==null) return 0;

		if(root.left==null&&root.right==null) {
			return 1;
		}
		return getLeafNodeCount(root.left)+getLeafNodeCount(root.right);
	}
	int getKLevelNodeCount(TreeNode root, int k) {
		//求K层的节点，转换成求k-1层的节点数量，还是子问题
		if(root==null) return 0;

		if(k==1) {
			return 1;
		}
		return getKLevelNodeCount(root.left,k-1)+
				getKLevelNodeCount(root.right,k-1);
	}

	//获取二叉树的高度
	int getHeight(TreeNode root) {
		if(root==null) return 0;
		//感觉这种子问题直接拿一个叶子节点，进行想象，然后代码就比较好写
		//也更加能够确定返回值的问题，以及要不要返回的问题
		int leftHeight=getHeight(root.left);
		int rightHeight=getHeight(root.right);
		return leftHeight>rightHeight ? leftHeight+1:rightHeight+1;
	}

	//检测值为value的元素是否在存在
	boolean find (TreeNode root,char val) {
		if(root==null) return false;

		//先找根节点，然后左节点，记录左子树的返回值
		if(root.val==val)
		{
			return true;
		}
		//这里不能这样写因为这不是比较两颗树是否相同
		//这里是找这个元素是不是在这颗树中
		//return find(root.left,val)&&find(root.right,val);
		boolean flg=find(root.left,val);
		if(flg==true) {
			return true;
		}
		boolean flg1=find(root.right,val);
		if(flg1==true) {
			return true;
		}
		//当代码走到这里的时候，说明压根就没有找到
		return false;
	}
	//层序遍历
	//这里还涉及几个问题，求一个二叉树最大的宽度和一个二叉树左视图和右视图
	void levelOrder(TreeNode root) {
		if(root==null) {
			return;
		}
		Queue<TreeNode> queue=new LinkedList<>();
		queue.offer(root);
		while(!queue.isEmpty()) {
			TreeNode cur=queue.poll();
			System.out.print(cur.val+" ");
			if(cur.left!=null) {
				queue.offer(cur.left);
			}
			if(cur.right!=null) {
				queue.offer(cur.right);
			}
		}
	}

	//判断一个二叉树是不是一个完全二叉树
	//先观察完全二叉树的特点，横着排列，但凡空后面有引用这个就不是一个完全二叉树
	boolean isCompleteTree (TreeNode root) {
		if(root==null) {
			return true;
		}
		Queue<TreeNode> queue =new LinkedList<>();
		queue.offer(root);
		while(!queue.isEmpty()) {
			TreeNode cur=queue.poll();
			if(cur!=null) {
				//当代码走到这里时候，不管他们左右孩子节点是否为空我们都将他们压入栈中
				queue.offer(cur.left);
				queue.offer(cur.right);
			}  else {
				//当代码走到这里，我们应该比较，后面有没有引用了
				//如果后面都是空的话，就是完全二叉树
				break;
				//当内层还有一个while循环的时候，并不会直接退出判断这个队列是否为空的循环
				//而是继续进入队列，继续弹出，此时队列为空，所以才会判断为true
			}
		}
		while(!queue.isEmpty()) {
			TreeNode cur=queue.poll();
			if(cur!=null) {
				return false;
			}
		}
		return true;
	}

	//我们可以借助这个来求出这个二叉树的最大宽度以及左视图和右视图。
	List<List <TreeNode>> levelOrder1(TreeNode root) {
		List<List <TreeNode>> ret=new ArrayList<>();
		if(root==null) {
			return null;
		}
		Queue<TreeNode> queue=new LinkedList<>();
		queue.offer(root);
		while(!queue.isEmpty()) {
			List<TreeNode> tmp=new ArrayList<>();
			int size= queue.size();
			while(size!=0) {
				TreeNode cur=queue.poll();
				tmp.add(cur);
				if(cur.left!=null) {
					queue.offer(cur.left);
				}
				if(cur.right!=null) {
					queue.offer(cur.right);
				}
				size--;
			}
			ret.add(tmp);
		}
		return ret;
	}
	//非递归的前序遍历
	public void preOrderNor(TreeNode root) {
		if(root==null) return ;
		Stack<TreeNode > stack =new Stack<>();
		TreeNode cur=root;
		TreeNode top=null;
		while(cur!=null||!stack.empty()) {
			while(cur!=null) {
				stack.push(cur);
				System.out.print(cur.val+" ");
				cur=cur.left;
			}
			top=stack.pop();
			cur=top.right;
		}
	}
	//非递归的中序遍历
	public void inOrderNor(TreeNode root) {
		if(root==null) return;
		Stack<TreeNode > stack =new Stack<>();
		TreeNode cur=root;
		TreeNode top=null;

		while(cur!=null||!stack.empty()) {
			while (cur != null) {
				stack.push(cur);
				cur = cur.left;
			}
			top=stack.pop();
			System.out.print(top.val+" ");
			cur=top.right;
		}
	}
	//非递归的后序遍历
	//注意这里面有坑，会导致程序一直在死循环
	public void postOrderNor(TreeNode root) {
		if(root==null) return ;
		Stack<TreeNode > stack =new Stack<>();
		TreeNode cur=root;
		TreeNode top=null;
		TreeNode prev=null;
		while(cur!=null || !stack.empty()) {
			while(cur!=null) {
				stack.push(cur);
				cur=cur.left;
			}
			//走到这里说明cur的左子树为空，此时进行右子树的遍历
			//先观察一下，如果右子树也为空的直接弹出元素并进行打印
			top=stack.peek();
			//当在进行观察的时候，我们同时也要观察top.right是不是等于上次的top
			//所以我们此时就需要一个prev来记录上次top值，
			//如果等于，直接进入程序，继续弹出栈顶的元素
			//否则的话，程序将一直进入死程序。
			if(top.right==null|| top.right==prev) {
				stack.pop();
				System.out.print(top.val+" ");
				prev=top;
			} else {
				cur=top.right;
			}
		}
	}
	//这是通过一个栈来找一个节点在哪里，没有任何的提示比大小之类的
	public boolean getpath(TreeNode root,TreeNode p,Stack<TreeNode> st1) {
		if(root==null ) {
			return false;
		}
		st1.push(root);
		if(root==p) {
			return true;
		}
		boolean flg1=getpath(root.left,p,st1);
		if(flg1) {
			return true;
		}
		boolean flg2=getpath(root.right,p,st1);
		if(flg2) {
			return true;
		}
		st1.pop();
		return false;
	}
	public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
		if(root==null) {
			return null;
		}
		Stack<TreeNode> st1=new Stack();
		Stack<TreeNode> st2=new Stack();

		getpath(root,p,st1);
		getpath(root,q,st2);
		//之后就是对栈进行操作了
		int len1=st1.size();
		int len2=st2.size();
		int cnt=len1-len2;
		if(len1-len2<0) {
			cnt=len2-len1;
			while(cnt!=0) {
				st2.pop();
				cnt--;
			}
		} else {
			while(cnt!=0) {
				st1.pop();
				cnt--;
			}
		}
		while(!st1.isEmpty()&&!st2.isEmpty()) {
			if(st1.peek().equals(st2.peek())) {
				return st1.peek();
			}
			st1.pop();
			st2.pop();
		}
		return null;
	}
	//找最近的公共祖先
	//递归的方式
	public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
		if(root==null) {
			return null;
		}
		if(p==root || q==root) {
			return root;
		}
		TreeNode leftTree=lowestCommonAncestor(root.left,p,q);
		TreeNode rightTree=lowestCommonAncestor(root.right,p,q);
		if(leftTree!=null&&rightTree!=null) {
			return root;
		} else if (leftTree!=null){
			return leftTree;
		} else {
			return rightTree;
		}
	}
	//根据前序遍历的结果和中序遍历的结果来构建这个二叉树
	//首先前序先能确定根，之后拿着这个根，在中序遍历中找左右子树，
	//此时前序前序遍历中i++，又拿到一个根，然后在中序遍历中找到这个根的左右子树。
	public int preindex;
	public TreeNode buildTree(int[] preorder, int[] inorder) {
		return buildTreeChild(preorder,inorder,0,inorder.length-1);
	}
	public TreeNode buildTreeChild(int [] preorder,int []inorder,int inbegin,int inend) {
		if(inbegin>inend) {
			return null;
		}
		TreeNode root=new TreeNode(preorder[preindex]);
		int index=find(preorder[preindex],inorder,inbegin,inend);
		if(index<0) {
			return null;
		}
		preindex++;
		root.left=buildTreeChild(preorder,inorder,inbegin,index-1);
		root.right=buildTreeChild(preorder,inorder,index+1,inend);
		return root;

	}
	public int find(int len,int [] inorder,int inbegin,int inend) {
		for(int i =inbegin;i<=inend;i++) {
			if(len==inorder[i]) {
				return i;
			}
		}
		return -1;
	}
}